package mr

import (
	"bytes"
	"container/heap"
	"runtime"
	"strconv"
	"sync"
	"time"
)

// 并发安全的延时队列

type DelayQueueInterface interface {
	Delay() int64
	Expired() time.Time
	Done() bool
}

type Elements []DelayQueueInterface

type DelayQueue struct {
	mu        sync.Mutex
	available sync.Cond
	leader    interface{}
	A         Elements
}

func (p *DelayQueue) Offer(x interface{}) {
	p.mu.Lock()
	defer p.mu.Unlock()
	heap.Push(&p.A, x)

	if p.Peek().(DelayQueueInterface).Delay() == x.(DelayQueueInterface).Delay() {
		p.leader = nil
		p.available.Signal()
	}
}

func (p *DelayQueue) Poll() interface{} {
	p.mu.Lock()
	defer p.mu.Unlock()

	defer func() {
		if p.leader == nil && p.Peek() != nil {
			p.available.Signal()
		}
	}()

	for {
		first := p.Peek()
		if first == nil {
			p.available.Wait()
		} else {
			delay := first.(DelayQueueInterface).Delay()
			if delay <= 0 {
				return heap.Pop(&p.A)
			}
			first = nil
			if p.leader != nil {
				p.available.Wait()
			} else {
				id := goroutineID()
				p.leader = id
				time.Sleep(time.Duration(delay) * time.Millisecond)
				if p.leader == id {
					p.leader = nil
				}
			}
		}
	}
}

func (p *DelayQueue) Init() {
	heap.Init(&(p.A))
}

func (p *DelayQueue) IsEmpty() bool {
	return len(p.A) == 0
}

func (p *DelayQueue) Peek() interface{} {
	if p.IsEmpty() {
		return nil
	}
	return (p.A)[0]
}

func (p *Elements) Push(x interface{}) {
	(*p) = append((*p), x.(DelayQueueInterface))
}

func (p *Elements) Pop() interface{} {
	n := p.Len()
	res := (*p)[n-1]
	(*p) = (*p)[0 : n-1]
	return res
}

func (p *Elements) Len() int {
	return len(*p)
}

func (p *Elements) Less(i, j int) bool {
	x := (*p)[i]
	y := (*p)[j]
	return x.Expired().Before(y.Expired())
}

func (p *Elements) Swap(i, j int) {
	(*p)[i], (*p)[j] = (*p)[j], (*p)[i]
}

func goroutineID() uint64 {
	b := make([]byte, 64)
	b = b[:runtime.Stack(b, false)]
	b = bytes.TrimPrefix(b, []byte("goroutine "))
	b = b[:bytes.IndexByte(b, ' ')]
	n, _ := strconv.ParseUint(string(b), 10, 64)
	return n
}

type Task struct {
	expired time.Time
	id      string
}

func (t *Task) Delay() int64 {
	return (int64)(t.expired.Sub(time.Now()).Seconds())
}

func (t *Task) Expired() time.Time {
	return t.expired
}

func (t *Task) Done() bool {
	return false
}
